package leetcode.primary;

import java.util.ArrayList;
import java.util.List;

public class T279 {
    List<Integer> nums;
    public int numSquares(int n) {
        nums = new ArrayList<>();
        int minCount = n;
        int i = 0;
        while (i*i<=n){
            nums.add(i*i);
            i++;
        }
        for (int j = nums.size()-1; j >0 ; j--) {
            int count = n/nums.get(j);
            if (count>minCount){
                break;
            }
            int remain = n%nums.get(j);
            int temp = remain;
            if (remain!=0){
                for (int k = j-1; k>0; k--) {
                    int temp_k = getCount(k,remain);
                    if (temp>temp_k){
                        temp = temp_k;
                    }
                }
                count+=temp;
            }
            System.out.println("j="+j+",count="+count);
            if (count<minCount){
                minCount = count;
            }
        }
        return minCount;

    }

    private int getCount(int i,int n){
        int count = n/nums.get(i);
        int remain = n%nums.get(i);
        if (remain!=0){
            return count+getCount(i-1,remain);
        }
        return count;
    }

    public static void main(String[] args) {
        T279 t279 = new T279();
        int i = t279.numSquares(4);
        System.out.println(i);
    }

}
